Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
LinkedIn Hard
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Closest Binary Search Tree Value II

Problem Statement

Given the root of a binary search tree, an integer target, and an integer k, return a 1D array containing k values from the BST which are closest to the given target value. You may return the answer in any order.

Examples

  • Example 1:
    • Input: BST = [10,5,15,2,7,null,18], target = 8.5, k = 3
Image
  • Expected Output: [7,10,5]

  • Justification: The three numbers closest to 8.5 in the BST are 7, 10, and 5.

  • Example 2:

    • Input: BST = [20,10,30,5,15,null,null,3,8,null,17], target = 15.5, k = 2
Image
  • Expected Output: [15,17]

  • Justification: The two numbers closest to 15.5 in the BST are 15 and 17.

  • Example 3:

    • Input: BST = [4,2,6,1,3,5,7], target = 4.5, k = 1
Image
  • Expected Output: [4]
  • Justification: The number closest to 4.3 in the BST is 4.

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 109
  • -109 <= target <= 109

Solution

To solve this problem, we begin by leveraging the natural order of binary search trees (BSTs) to find the k values closest to a given target. The key insight here is to use an in-order traversal of the BST, which naturally visits the nodes in ascending order. This methodical approach allows us to access each value within the tree systematically, ensuring that we can compare each value directly against the target. By collecting all values in a list through this traversal, we position ourselves to efficiently determine which values are closest to the target by examining their absolute differences from the target.

Once we have the list of values from the in-order traversal, the next step involves sorting this list based on each value's proximity to the target. This sorting is done by calculating the absolute difference between the target and each value in the list. After sorting, the first k elements of this list represent the closest values to the target. This approach is effective because it combines the inherent ordered nature of the BST with a sorting mechanism that prioritizes closeness to the target.

Step-by-step Algorithm

  1. Initialize: Start by creating a list, values, to store the values of all nodes in the binary search tree (BST).

  2. In-order Traversal:

    • Recursively perform an in-order traversal of the BST.
    • During the traversal, visit the left child, the node itself, and then the right child in this order.
    • Add each node’s value to the values list. This step ensures that the values are stored in sorted order because of the BST’s properties.
  3. Sorting by Proximity:

    • After completing the in-order traversal, you will have a list of all node values in sorted order.
    • Sort the values list based on the absolute difference from the target value. This rearrangement prioritizes the values closest to the target.
  4. Selecting Closest Values:

    • Once the list is sorted by proximity to the target, select the first k elements from this list.
    • These k elements are the closest values to the target.
  5. Return the Result:

    • Return the sublist containing the closest k values to the target.

Algorithm Walkthrough

Let's consdier the given input:

        20
       /  \
      10  30
     /  \
    5   15
   / \    \
  3   8    17

target = 15.5, and k = 2.

  1. In-order Traversal:

    • Start with the root node 20, but since we are doing an in-order traversal, we first move to the left subtree.
    • At node 10, again move to the left subtree.
    • At node 5, move to its left child 3. Since 3 has no left child, it's the first node to visit.
      • Add 3 to values: [3]
    • Back to 5, now visit it.
      • Add 5 to values: [3,5]
    • Move to 5's right child 8 and visit it.
      • Add 8 to values: [3,5,8]
    • Having visited 5 and its children, go back to 10 and visit it.
      • Add 10 to values: [3,5,8,10]
    • Visit 10's right child 15, but since 15 has a right child 17, we first visit 17.
      • Add 15 to values after 17: [3,5,8,10,17,15]
    • With the left subtree fully visited, move to the root 20 and visit it.
      • Add 20 to values: [3,5,8,10,15,17,20]
    • Finally, visit the right subtree, which is just node 30.
      • Add 30 to values: [3,5,8,10,15,17,20,30]
  2. Sorting by Proximity to Target (15.5):

    • Sort values by the absolute difference from 15.5, resulting in [15,17,10,8,20,5,3,30].
  3. Selecting Closest Values (k=2):

    • After sorting by proximity, the closest values to 15.5 are 15 and 17.
    • Thus, we correctly identify [15,17] as the k=2 closest values to the target.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • In-order Traversal: The in-order traversal of the BST has a time complexity of , where (N) is the number of nodes in the BST. This is because each node in the tree is visited exactly once.
  • Sorting: After collecting all node values, the list is sorted based on the absolute difference from the target value. The sort operation has a time complexity of in the average and worst case.
  • Extracting the (k) Closest Values: Extracting the first (k) elements from the sorted list has a time complexity of , which is negligible compared to the sorting step for large (N).

Therefore, the overall time complexity of the solution is due to the sorting step being the most significant factor.

Space Complexity

  • In-order Traversal Storage: The space complexity is due to the storage of all (N) node values in a list or array.
  • Recursive Stack Space: In the case of the recursive in-order traversal, there's additional space complexity due to the call stack. However, in a balanced BST, this would be . In the worst case (a completely unbalanced tree), it could be .
Closest Binary Search Tree Value II (hard)
Word Ladder (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity